Keywords: GMW protocol, optimizations, privacy-preserving face recognition

ABSTRACT

提出了两种方案：Yao's garbled circuits 和GMW协议。 但因为Yao但方案有constant round complexity，所以大多数研究都表明其有更好的效率。

这篇文章提出了一些GMW协议的优化。 总结了depth-optimized circuit constructions. 还考虑了隐私保护的人脸识别(privacy-preserving face recognition)

1 Introduction

• Yao's garbled circuits, GMW: 都把函数表示为Boolean circuit，都提供security against semi-honest adversaries.

• semi-honest adversaries: honestly follow the protocol but try to learn additional information from observed messages.

• Yao's protocol:
  • a constant number of rounds
  • requires OTs only for the input of one of the parties 只有一方的输入需要OT
  • secure evaluation of a gate: requires only symmetric cryptographic operations 计算门时只需要对称密码技术

• GMW protocol:
  • requires an interactive OT for each AND gate 对每一个AND门都要求交互式的OT协议

Contributions

GMW协议在two semi-honest parties中是可行的。 此外，GMW协议相对于Yao's的协议有一些额外的优势。

• three

2 Preliminaries

2.1 Oblivious Transfer

在1-out-of n $\mathrm{OT}_l^m$中： S：提供m个n元组 R：提供m个选择 最后R会根据每一个选择得到元组中的一个数字。

• Naor-Pinkas OT protocol

  [25]Naor, M., Pinkas, B.: Computationally secure oblivious transfer. Journal of Cryptology 18(1), 1–35 (2005)

  • secure against semi-honest adversaries
  • under Decisional Diffie-Hellman(DDH) assumption
  • in the random-oracle model
  • requires both parties to perform $\mathcal{O(m)}$modular exponentiations

• 有两种加速OT的方法

  • OT pre-computations

    [2]Beaver, D.: Precomputing oblivious transfer. In: Advances in Cryptology - CRYPTO’95. LNCS, vol. 963, pp. 97–109. Springer (1995)

    • offline: pre-compute the OTs on random inputs
    • online: use pre-computed values as one-time pads to run the OT on the actual inputs.
      • R: sends one message of m $\log_2n$ bits to S（隐藏选择）
      • S: sends back a message of size mnl bits

  • OT extensions

    [16,22]

2.2 Approaches for Secure Two-Party Computation

2.2.1 Yao's Garbled Circuits Protocol

[33]Yao, A.C.: How to generate and exchange secrets. In: Foundations of Computer Science (FOCS’86). pp. 162–167. IEEE (1986)

Yao's protocol: 1. non-interactively 2. has a constant number of rounds

• creator（电路生成方）：encrypt the function to be computed

  For each gate:

  1. map the plain values to random-looking symmetric keys
  2. generate an encryption table

     通过该表，可以用给定的input keys计算gate's output key

  3. transmit the encrypted circuit and (creator's) encrypted inputs to evaluator

• evaluator（电路计算方）
  4. obtains his encrypted input via 1-out-of 2 OT (evaluator's input key)
  5. use the encrypted inputs to evaluate the encrypted function gate by gate

• creator
  7. provides a mapping from the encrypted output to plain output

some extension

2.2.2 GMW Protocol

[11]Goldreich, O.: Foundations of Cryptography, vol. 2: Basic Applications. Cambridge University Press (2004) [12]Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Symposium on Theory of Computing (STOC’87). pp. 218–229. ACM (1987)

GMW protocol: interactively compute a function using secret-shared values

• share each input and intermediate wire to 2 parties

  用2-out-of-2 secret sharing sheme把value v 分享给两方，每一方得到的一个random-looking share $v_i$

  • $v = v_1\oplus v_2$

• XOR gates: securely evaluated locally by XORing the shares

• AND gates: parties run an interactively protocol

• output wire:

  把和output wire相关的shares发送给需要得到output的参与方，计算output

• AND gate: 两种实现方法

  • Oblivious Transfer

  • Multiplication Triples

    [1] Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a com- pleteness theorem for protocols with honest majority. In: Symposium on Theory of Computing (STOC’87). pp. 218–229. ACM (1987)

2.3 Evaluation Metrics and Notation

因为Yao's和GMW都提供free XORs，因此只比较AND gates

• size S(C) : the number AND gates in circuit C

• depth D(C): the maximum number of AND gates

• other notations:

3 Circuit Constructions with low Depth and Size

3.1 Addition

linear size and depth

[18]Ripple-carry adder: Kolesnikov, V., Sadeghi, A.R., Schneider, T.: Improved garbled circuit building blocks and applications to auctions and computing minima. In: Cryptology And Network Security (CANS’09). LNCS, vol. 5888, pp. 1–20. Springer (2009)

3.1.1 Ladner-Fscher Adder.

[21] Ladner-Fischer adder Ladner,R.E.,Fischer,M.J.:Parallelprefixcomputation.JournaloftheACM27(4), 831–838 (1980)

in logarthmic depth

3.1.2 Carry-Save Adder

[8] carry-save adder: Earle, L.G.: Latched carry-save adder. IBM Technical Disclosure Bulletin 7(10), 909–910 (1965)

has linear size and constant depth

3.2 Squaring

a squaring circuit is smaller by a factor of about 2 $x_jx_i+x_ix_j = 2x_ix_j$ $x_ix_i=x_i$

3.3 Comparison

• equal:

• greater than:

3.4 Hamming Weight

4 Optimizations for Two Party GMW

an implementation of GMW [5]Choi, S.G., Hwang, K.W., Katz, J., Malkin, T., Rubenstein, D.: Secure multi-party computation of Boolean circuits with applications to privacy in on-line market- places. In: Cryptographers’ Track at the RSA Conference (CT-RSA’12). LNCS, vol. 7178, pp. 416–432. Springer (2012)

currently fastest garbled circuits implementation [15] Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: Security Symposium. USENIX (2011)

[5]能在n≥3时高效实现GMW协议，对于n=2的情况，[5]认为他们的速度会比当前最快的garbled circuits实现慢两倍。

Benchmarking Environment

• evaluate the time for: using average time for 100 executions
  • setup phase:
    • Naor-Pinkas OTs: group $\Z_p^*$with $|p|=512$ bit
    • OT extension: security parameter t = $80$
  • online phase:
    • sharing of inputs
    • circuit evaluation
    • combining output shares
  • overall time:
    • circuit construction
    • setup phase
    • online phase

• circuit: an unoprmized 512-bit multiplication circuit C
  • S(C) = 800,227
  • D(C)=38

• PC:

  

Table 1: Time improvements

list the modifications in the order. each modification include the improvement of all previous optimizations.

4.1 Multiplication Triples

[1] multiplication triples Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Ad- vances in Cryptology – CRYPTO’91. LNCS, vol. 576, pp. 420–432. Springer (1991)

• Beaver's MT: (instead of pre-computed OTs)
  • slightly slower in setup phase
  • more efficient in online phase

time:

4.2 Using ASE instead of SHA as Pseudo-Random Function

• SHA-1 in original implementation：
  • instantiant the random oracle
  • generate pseudo-random values in the OT extension

• ASE (CTR mode) as PRF:
  • decreased the number of expensive hash function calls per AND gate 降低了每个AND门调用的hash函数次数
    • receiver R: from 3.5 to 1
    • sender S: from 4.5 to 4
  • numer of calls to instantiate the PRF 实例化PRF需要调用AES的次数
    • R: 3.1 AES calls per AND gate
    • S: 0.65 AES calls per AND gate
  • the sender and the receiver have different computational workload

Table 2: Comparison of SHA-1 and AES128 implementation

4.3 Load Balancing

• run the OTs in either direction, each party has the same workload 因为MT在online phase 是对称形式的，所以可以双方各自并行运行OT协议
  • 2.5 SHA-1 invoations per AND gate
  • 1.8 AES invocations per AND gate

run the Naor-Pinkas OT protocol for the seed OTs twice, which however amortizes fairly quickly 虽然运行了两次，但非常快。

• four parallel threads during setup phase
  • one for pseudo-random function
  • the other for random oracle

time:

4.4 Implementation-Specific Optimizations

• arithmetic for modular arithmetics
  • use GMP

• bitwise processing order during OT extension and online phase
  • perform operations bytewise 按字节异或，而不是按位

• SHA-1 for the random oracle
  • use an assembler implementation of OpenSSL

time:

4.5 Single Instruction Multiple Data (SIMD) Operations